一、DIFFPOLL [2018]

《Hierarchical Graph Representation Learning with Differentiable Pooling》

1. 当前GNN 架构的主要局限性在于它们本质上是平的（flat），因为它们仅仅跨图的边来传播信息，并且无法以层次（hierarchical）的方式推断和聚合信息。这种缺乏层次结构的情况对于graph 分类任务尤其成为问题。当GNN 应用到图分类时，标准方法是为图中的所有节点生成 embedding，然后将所有这些节点 embedding 执行全局池化。这种全局池化忽略了图中可能存在的任何层次结构，并阻碍了人们为 graph-level 预测任务建立有效的 GNN 模型。

   论文 《Hierarchical Graph Representation Learning with Differentiable Pooling》 提出了 DIFFPOOL，这是一种可微分的graph pooling 模块，可以通过层次的、端到端的方式适应各种 GNN 架构，如下图所示。DIFFPOOL 允许开发更深的 、可以学习操作图的层次表示（hierarchical representation）的 GNN模型。

   下图中，在每个层次的 layer 上运行一个 GNN 模型来获取节点 embedding。然后，DIFFPOOL 使用这些学到的 embedding 将节点聚类到一起，并在这个粗化的图上运行另一个 GNN layer 。重复 $L$$L$ 次，并使用最终的输出 representation 来对图进行分类。

   

   DIFFPOOL 类似于 CNN 的空间池化。和标准的 CNN 相比，GNN 面临的挑战是：

   • 首先，graph 不包含自然的空间局部性概念，即不能简单的在graph 上对一个 $n\times n$$n\times n$ 的 patch 上的所有节点进行池化，因为图的复杂拓扑结构使得无法定义 patch 。

   • 其次，和图像数据不同，图数据集通常包含数量变化的节点和边的图，这使得定义图池化运算更具挑战性。

   为解决上述挑战，我们需要一个模型，该模型学习如何将节点聚类在一起从而在底层图之上搭建一个层次的 multi-layer 结构。

   DIFFPOOL 方法在GNN 的每一层上学习可微的 soft assignment，并根据其学到的 embedding 将节点映射到簇。在 DIFFPOOL 框架中，我们通过以层次的方式堆叠 GNN layer ，从而生成 deep GNN ：第 $l$$l$ 层的输入节点对应于第 $l-1$$l-1$ 层学到的簇。因此，DIFFPOOL 的每一层都将输入图越来越粗化，并且 DIFFPOOL 能够在训练后生成任何输入图的hierarchical representation。

   实验表明：DIFFPOOL 可以和各种 GNN 方法结合使用，从而使得平均准确率提高 7%，并且在五个benchmark 中的四个达到了 SOTA 性能。

   最后，论文证明 DIFFPOOL 可以学习和输入图中定义明确的社区相对应的、可解释的层次聚类。

2. 相关工作：

   • 通用的图神经网络：近年来提出了各种各样的图神经网络模型。这些方法大多符合 《Neural message passing for quantum chemistry》提出的 "neural message passing"的框架。在消息传递框架中，GNN 被看作是一种消息传递算法，其中 node representation 是使用可微聚合函数从其邻居节点的特征中反复计算出来的。

     《Representation learning on graphs: Methods and applications》对该领域的最新进展进行了回顾， 《Geometric deep learning:Going beyond euclidean data》概述了图神经网络与谱图卷积（spectral graph convolution）的联系。

   • 基于图神经网络的图分类：图神经网络已经被应用于各种任务，包括节点分类、链接预测、图分类、和化学信息学。在图分类的背景下应用 GNN 的一个主要挑战是如何从 node embedding 到整个图的 representation 。解决这个问题的常见方法包括：

     • 在网络最后一层简单地求和或平均所有的 node embedding 。

     • 引入一个与图中所有节点相连的 "virtual node"。

     • 使用一个能够操作集合的深度学习架构来聚合 node embedding。

     然而，所有这些方法都有一个局限性，即它们不学习 hierarchical representation （即所有的 node embedding 都在单个 layer 中被全局地池化），因此无法捕捉到许多现实世界中图的自然结构。最近的一些方法也提出了将 CNN 架构应用于所有node embedding 的拼接，但这需要指定（或学习）节点的典型排序（一般来说这非常困难，相当于解决图的同构性graph isomorphism ）。

1.1 模型

1. DIFFPOOL 的关键思想是：通过提供可微的模块来层次地池化图节点，从而构建深度的 multi-layer GNN 模型。

2. 给定图 $\mathcal{G}=(\mathbf{X},\mathbf{A})$$\mathcal G=(\mathbf X,\mathbf A)$，其中：

   • 每个节点 $v_i$$v_i$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec x}_i\in \mathbb R^{d }$ ，所有节点的特征向量组成特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{n\times d}$$\mathbf X\in \mathbb R^{n\times d }$ 。$n$$n$ 为节点数量，$d$$d$ 为特征相邻维度。

     为方便讨论，我们将所有维度（包括输入特征维度和 embedding 向量维度）都设为 $d$$d$ ，实际应用中可以采用不同的维度。

   • $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ 为邻接矩阵，其中 $A_{i,j}$$A_{i,j}$ 表示节点 $v_i,v_j$$v_i,v_j$ 之间的连接权重。当 $A_{i,j}=0$$A_{i,j}=0$ 表示 $v_i$$v_i$ 和 $v_j$$v_j$ 之间不存在连接。

     这里我们假设图是无权重的，即 $A_{i,j}\in \{0,1\}$$A_{i,j}\in \{0,1\}$ 。

   注意：这里我们未考虑边特征。

   给定一组带标签的图 $\mathcal{D}=\{({\mathcal{G}}_1,y_1),\cdots ,({\mathcal{G}}_N,y_N)\}$$\mathcal D=\left\{(\mathcal G_1,y_1),\cdots,(\mathcal G_N,y_N)\right\}$ ，其中 $y_i\in \mathcal{Y}$$y_i\in \mathcal Y$ 为第 $i$$i$ 个图 ${\mathcal{G}}_i\in \mathcal{G}$$\mathcal G_i\in \mathcal G$ 的标签。图分类任务的目标是学习graph 到label 的映射函数 $f:\mathcal{G}\to \mathcal{Y}$$f:\mathcal G\rightarrow \mathcal Y$ 。

   和标准的监督学习任务相比，这里的挑战是：我们需要一种从这些输入图中抽取有用的特征向量的方法。即，我们需要一个过程来将每个图转换为一个有限维的向量。

3. 本文我们以GNN 为基础，以端到端的方式学习图分类的有用representation。具体而言，我们考虑采用以下的 message-passing 架构的 GNN：

   $${\mathbf{H}}^{(k)}=\mathcal{M}(\mathbf{A},{\mathbf{H}}^{(k-1)};{\theta }^{(l)})$$

   其中：

   • ${\mathbf{H}}^{(k)}\in {\mathbb{R}}^{n\times d}$$\mathbf H^{(k)}\in \mathbb R^{n\times d}$ 为第 $k$$k$ 层的节点 embedding ，其中 ${\mathbf{H}}^{(0)}=\mathbf{X}$$\mathbf H^{(0)}=\mathbf X$ 为输入特征矩阵。

   • $\mathcal{M}(\cdot )$$\mathcal M(\cdot)$ 为消息传递函数，它依赖于邻接矩阵 $\mathbf{A}$$\mathbf A$ 、第 $k-1$$k-1$ 层的节点 embedding ${\mathbf{H}}^{(k-1)}$$\mathbf H^{(k-1)}$ 、以及可训练的参数 ${\theta }^{(k)}$$\theta^{(k)}$ 。

   我们提出的可微池化模块可以应用于任何 GNN 模型，并且对于如何实现 $\mathcal{M}(\cdot )$$\mathcal M(\cdot)$ 的细节是不可知的。

4. 消息传递函数 $\mathcal{M}(\cdot )$$\mathcal M(\cdot)$ 有多种可能的形式，例如 GCN 中采用一个线性映射和一个 ReLU 非线性激活函数来实现：

   $${\mathbf{H}}^{(k)}=\mathcal{M}(\mathbf{A},{\mathbf{H}}^{(k-1)};{\theta }^{(k)})=\text{ReLU}\left({\tilde{\mathbf{D}}}^{-1/2}\tilde{\mathbf{A}}{\tilde{\mathbf{D}}}^{-1/2}{\mathbf{H}}^{(k-1)}{\mathbf{W}}^{(k)}\right)$$

   其中：

   • $\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}$$\tilde{\mathbf A} = \mathbf A + \mathbf I$ 为带自环的邻接矩阵，$\tilde{\mathbf{D}}$$\tilde{\mathbf D}$ 为对应的邻接矩阵，它是一个对角矩阵，满足 ${\tilde{D}}_i=\sum _j{\tilde{A}}_{i,j}$$\tilde D_i=\sum_j \tilde A_{i,j}$ 。

   • ${\mathbf{W}}^{(k)}\in {\mathbb{R}}^{d\times d}$$\mathbf W^{(k)}\in \mathbb R^{d\times d}$ 为可训练的权重矩阵。

5. 完整的 GNN 模块可能包含 $K$$K$ 层，最终输出的节点 embedding 为 $\mathbf{Z}={\mathbf{H}}^{(K)}\in {\mathbb{R}}^{n\times d}$$\mathbf Z=\mathbf H^{(K)}\in \mathbb R^{n\times d}$ ，其中 $K$$K$ 通常为2~6 层。

   为简化讨论，在后续内容中，我们将忽略GNN 的内部结构，并使用 $\mathbf{Z}=\text{GNN}(\mathbf{A},\mathbf{X})$$\mathbf Z=\text{GNN}(\mathbf A, \mathbf X)$ 来表示一个任意的 GNN 模块，它根据邻接矩阵 $\mathbf{A}$$\mathbf A$ 和输入特征矩阵 $\mathbf{X}$$\mathbf X$ 进行了 $K$$K$ 轮消息传递。

6. 上述GNN 的本质上是 flat 的，因为它们仅在图的边之间传播信息。我们的目标是定义一种通用的、端到端的可微策略，该策略允许人们以层次化的方式堆叠多个 GNN 模块。

   形式上，给定一个邻接矩阵 $\mathbf{A}\in {\mathbb{R}}^{n\times n}$$\mathbf A\in \mathbb R^{n\times n}$ 以及一个 GNN 模块的输出 $\mathbf{Z}=\text{GNN}(\mathbf{A},\mathbf{X})$$\mathbf Z=\text{GNN}(\mathbf A, \mathbf X)$，我们试图寻找一种策略，该策略输出包含 $m<n$$m\lt n$ 个节点的新的粗化图。粗化图具有加权邻接矩阵 ${\mathbf{A}}^{\prime }\in {\mathbb{R}}^{m\times m}$$\mathbf A^\prime\in \mathbb R^{m\times m}$ ，以及新的节点 embedding ${\mathbf{Z}}^{\prime }\in {\mathbb{R}}^{m\times d}$$\mathbf Z^\prime \in \mathbb R^{m\times d}$ 。

   然后，而可以将这个新的粗化图用作另一个 GNN layer 的输入，并且可以将整个过程重复 $K$$K$ 次，从而生成具有 $K$$K$ 个 GNN layer 的模型，该模型对输入图的一系列越来越粗的版本进行操作。因此，我们的目标是学习如何使用 GNN 的输出将节点聚类在一起，以便我们可以将这个粗化图用作另一个 GNN layer 的输入。

   和常规的图粗化任务相比，为 GNN 设计这样的池化层尤其具有挑战性的原因是：我们的目标不是简单地将一个图中的节点聚类，而是提供一个通用的方法对输入图的一组广泛的节点进行层次池化（hierarchically pool）。即，我们需要模型来学习一种池化策略，该策略将在具有不同节点、边的图之间进行泛化，并且在推断过程中可以适配各种图结构。

1.1.1 DIFFPOOL 方法

1. DIFFPOOL 方法通过使用 GNN 模型的输出来学习节点上的cluster assignment 矩阵来解决上述挑战。关键的直觉是：我们堆叠了 $L$$L$ 个 GNN 模块，其中基于第 $l-1$$l-1$ 层的 GNN 生成的 embedding 并以端到端的方式学习如何将节点分配给第 $l$$l$ 层的簇。

   因此，我们不仅使用 GNN 来抽取对graph 分类有用的节点 embedding，也使用 GNN 来抽取对层次池化有用的节点 embedding 。通过这种方式，DIFFPOOL 中的 GNN 学会编码一种通用的池化策略。

   我们首先描述 DIFFPOOL 模块如何在给定assignment 矩阵的情况下在每一层上池化节点，接下来我们讨论如何使用 GNN 架构生成assignment 矩阵。

2. 给定 assignment 矩阵的池化：我们将第 $l$$l$ 层学到的cluster assignment 矩阵定义为 ${\mathbf{S}}^{(l)}\in {\mathbb{R}}^{n_l\times n_{l+1}}$$\mathbf S^{(l)}\in \mathbb R^{n_l\times n_{l+1}}$ ，其中 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 中的每一行表示第 $l$$l$ 层的节点或簇、每一列表示第 $l+1$$l+1$ 层的簇。直观地讲，${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 将第 $l$$l$ 层的每个节点软分配（soft assignment）给下一个粗化的、第 $l+1$$l+1$ 层中的簇。

   假设 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 已经计算好，即我们已经在模型的第 $l$$l$ 层计算好了assignment 矩阵。我们假设第 $l$$l$ 层的输入邻接矩阵为 ${\mathbf{A}}^{(l)}$$\mathbf A^{(l)}$、第 $l$$l$ 层的输入节点embedding 矩阵为 ${\mathbf{Z}}^{(l)}$$\mathbf Z^{(l)}$。给定这些输入，DIFFPOOL 层将粗化coarsen 输入图，生成一个新的粗化的邻接矩阵 ${\mathbf{A}}^{(l+1)}$$\mathbf A^{(l+1)}$、以及新的粗化的节点 embedding 矩阵 ${\mathbf{X}}^{(l+1)}$$\mathbf X^{(l+1)}$ 。即：

   $$\begin{array}{c}({\mathbf{A}}^{(l+1)},{\mathbf{X}}^{(l+1)})=\text{DIFFPOOL}({\mathbf{A}}^{(l)},{\mathbf{Z}}^{(l)})\\ {\mathbf{X}}^{(l+1)}={\mathbf{S}}^{(l{)}^{\mathrm{\top }}}{\mathbf{Z}}^{(l)}\in {\mathbb{R}}^{n_{l+1}\times d}\\ {\mathbf{A}}^{(l+1)}={\mathbf{S}}^{(l{)}^{\mathrm{\top }}}{\mathbf{A}}^{(l)}{\mathbf{S}}^{(l)}\in {\mathbb{R}}^{n_{l+1}\times n_{l+1}}\end{array}$$

   其中：

   • DIFFPOOL 根据cluster assignment 矩阵 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 来聚合节点 embedding ${\mathbf{Z}}^{(l)}$$\mathbf Z^{(l)}$ ，从而生成第 $l+1$$l+1$ 层的 $n_{l+1}$$n_{l+1}$ 个簇的 embedding 。

     物理意义：第 $l+1$$l+1$ 层的每个簇的 embedding 等于它包含的子节点的 embedding 的加权和，权重为子节点属于这个簇的可能性（由 assignment 矩阵给出）。

   • DIFFPOOL 根据cluster assignment 矩阵 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 和邻接矩阵 ${\mathbf{A}}^{(l)}$$\mathbf A^{(l)}$ 来生成粗化的邻接矩阵，这个粗化的邻接矩阵表示 cluser pair 对之间的连接强度。

     物理意义：第 $l+1$$l+1$ 层的任意两个簇之间的距离等于各自包含的子节点之间距离的加权和，权重为子节点属于各自簇的可能性（由 assignment 矩阵给出）。

   这样，DIFFPOOL 粗化了图：下一层邻接矩阵 ${\mathbf{A}}^{(l+1)}$$\mathbf A^{(l+1)}$ 表示具有 $n_{l+1}$$n_{l+1}$ 个节点或簇点（cluster node）的粗化图，其中每个簇点对应于第 $l$$l$ 层中的一个簇中所有的节点。

   注意：${\mathbf{A}}^{(l+1)}$$\mathbf A^{(l+1)}$ 是一个实数矩阵，它表示一个全连接的、带权的图。每一项 $A_{i,j}^{(l+1)}$$A^{(l+1)}_{i,j}$ 表示簇 $i$$i$ 和簇 $j$$j$ 之间的连接强度。类似地，${\mathbf{X}}^{(l+1)}$$\mathbf X^{(l+1)}$ 中的第 $i$$i$ 行对应于簇 $i$$i$ 的 embedding 。

   粗化的邻接矩阵 ${\mathbf{A}}^{(l+1)}$$\mathbf A^{(l+1)}$ 和簇 embedding ${\mathbf{X}}^{(l+1)}$$\mathbf X^{(l+1)}$ 一起可以用于另一个 GNN layer 的输入。我们接下来详述。

3. 学习 assignment 矩阵：现在我们描述DIFFPOOL 如何生成assignment 矩阵 ${\mathbf{S}}^{(l)}$$\mathbf S^{(l)}$ 和embedding 矩阵 ${\mathbf{Z}}^{(l)}$$\mathbf Z^{(l)}$ 。我们使用两个独立的 GNN 来生成这两个矩阵，这两个GNN 都作用到簇点特征 ${\mathbf{X}}^{(l)}$$\mathbf X^{(l)}$ 和粗化的邻接矩阵 ${\mathbf{A}}^{(l)}$$\mathbf A^{(l)}$ 上。

   • 第 $l$$l$ 层的 embedding GNN 是标准的 GNN 模块：

     $${\mathbf{Z}}^{(l)}={\text{GNN}}_{l,\text{embed}}({\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)})$$

     即，我们采用第 $l$$l$ 层簇点的邻接矩阵和特征矩阵，并用标准的 GNN 来获取簇点的新的 embedding 矩阵 ${\mathbf{Z}}^{(l)}$$\mathbf Z^{(l)}$ 。

   • 第 $l$$l$ 层的 pooling GNN 使用簇点的邻接矩阵和特征矩阵来生成 assignment 矩阵：

     $${\mathbf{S}}^{(l)}=\text{softmax}\left({\text{GNN}}_{l,\text{pool}}({\mathbf{A}}^{(l)},{\mathbf{X}}^{(l)})\right)$$

     其中 softmax 是逐行进行。

     ${\text{GNN}}_{l,\text{pool}}$$\text{GNN}_{l,\text{pool}}$ 的输出维度对应于第 $l$$l$ 层中预定义的最大簇数，并且是模型的超参数。

   注意：

   • 这两个 GNN 采用相同的输入数据，但是具有不同的参数化（parameterization）并发挥不同的作用：embedding GNN 为第 $l$$l$ 层输入节点生成新的 embedding；pooling GNN 为第 $l$$l$ 层输入节点生成对应于 $n_{l+1}$$n_{l+1}$ 个簇的分配概率。

   • 当 $l=0$$l=0$ 时，${\mathbf{A}}^{(0)}=\mathbf{A}$$\mathbf A^{(0)} = \mathbf A$ 为原始图的邻接矩阵，${\mathbf{X}}^{(0)}=\mathbf{X}$$\mathbf X^{(0)} = \mathbf X$ 为原始的输入特征矩阵。

   • 在倒数第二层 $(L-1)$$(L-1)$ 中，我们将assignment 矩阵 ${\mathbf{S}}^{(L-1)}$$\mathbf S^{(L-1)}$ 设置为一个全为1 的向量，即：将最后一层 $L$$L$ 中所有节点都分配给单个簇，从而生成对应于整个图的 final embedding 向量。

     然后可以将这个final embedding 向量用于可微分类器（如 softmax 层）的特征输入，并使用随机梯度下降来端到端地训练整个系统。

4. 排列不变性（permutation invariance）：注意，为了对图分类有用，池化层应该是节点排列不变的。对于 DIFFPOOL，我们得到以下正面的结论，这表明：只要GNN 的组件component 是排列不变的，那么任何基于 DIFFPOOL 的 deep GNN 模型都是排列不变的。

   推论：令 $\mathbf{P}\in \{0,1{\}}^{n\times n}$$\mathbf P\in \{0,1\}^{n\times n}$ 为任意的排列矩阵permutation matrix，则只要满足 $\text{GNN}(\mathbf{A},\mathbf{X})=\text{GNN}(\mathbf{P}\mathbf{A}{\mathbf{P}}^{\mathrm{\top }},\mathbf{X})$$\text{GNN}(\mathbf A,\mathbf X) = \text{GNN}\left(\mathbf P\mathbf A\mathbf P^\top,\mathbf X\right)$ ，则有 $\text{DIFFPOOL}(\mathbf{A},\mathbf{Z})=\text{DIFFPOOL}(\mathbf{P}\mathbf{A}{\mathbf{P}}^{\mathrm{\top }},\mathbf{P}\mathbf{X})$$\text{DIFFPOOL}(\mathbf A,\mathbf Z) = \text{DIFFPOOL}\left(\mathbf P\mathbf A\mathbf P^\top,\mathbf P\mathbf X\right)$ 。

   证明：假设 GNN 模块是排列不变的，则 ${\mathbf{Z}}^{(l)},{\mathbf{S}}^{(l)}$$\mathbf Z^{(l)}, \mathbf S^{(l)}$ 都是排列不变的。考虑到 $\mathbf{P}$$\mathbf P$ 的正交性（${\mathbf{P}}^{\mathrm{\top }}\mathbf{P}=\mathbf{I}$$\mathbf P^\top\mathbf P=\mathbf I$），应用到 ${\mathbf{X}}^{(l+1)},{\mathbf{A}}^{(l+1)}$$\mathbf X^{(l+1)},\mathbf A^{(l+1)}$ 的计算公式，则得证。

1.1.2 辅助链接预测和熵正则化

1. 在实践中，仅使用来自图分类任务的梯度信号来训练 pooling GNN 可能会很困难。直观地讲，我们有一个非凸优化问题，在训练初期很难将 pooling GNN 推离局部极小值。

   为缓解该问题，我们使用辅助的链接预测目标（auxiliary link prediction objective）训练 pooling GNN，该目标编码了先验知识：应该将相邻的节点映射到相同的簇。具体而言，在每一层 $l$$l$ ，我们最小化目标：

   $${\mathcal{L}}_{\text{LP}}={\Vert {\mathbf{A}}^{(l)}-{\mathbf{S}}^{(l)}{\mathbf{S}}^{(l{)}^{\mathrm{\top }}}\Vert }_F$$

   其中 $||\cdot |{|}_F$$||\cdot||_F$ 为Frobenius 范数。

   ${\mathbf{S}}^{(l)}{\mathbf{S}}^{(l{)}^{\mathrm{\top }}}$$\mathbf S^{(l)}\mathbf S^{(l)^\top}$ 给出任意两个节点位于相同簇中的可能性，如果它等于邻接矩阵那么表明：pooling GNN 将相连的节点分配到相同的簇、将不相连的节点分配到不同的簇。

   注意：邻接矩阵 ${\mathbf{A}}^{(l)}$$\mathbf A^{(l)}$ 是低层 assignment 矩阵的函数，并且在训练期间会不断改变。

2. pooling GNN 的另一个重要特点是：每个节点的输出cluster assignment 通常应该接近一个one-hot 向量，从而清楚地定义节点属于哪个cluster 。因此，我们通过最小化以下目标来对cluster assignment 的熵进行正则化：

   $${\mathcal{L}}_E=\frac{1}{n}\sum _{i=1}^{n}H({\overrightarrow{\mathbf{s}}}_i)$$

   其中：$H(\cdot )$$H(\cdot)$ 为熵函数；${\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec s}_i$ 为 assignment 矩阵 $\mathbf{S}$$\mathbf S$ 的第 $i$$i$ 行。

3. 在训练期间，来自每一层的 ${\mathcal{L}}_{\text{LP}},{\mathcal{L}}_E$$\mathcal L_\text{LP},\mathcal L_{E}$ 都添加到分类损失中。实践中我们观察到：带有这些额外目标的训练花费更长的时间才能收敛，但是获得了更好的性能以及更可解释的cluster assignment 。

1.2 实验

1. 我们针对多个SOTA 图分类方法评估了 DIFFPOOL 的优势，目的是回答以下问题：

   • Q1：DIFFPOOL 对比其它 GNN 中的池化方法（如 sort pooling 或者 Set2Set 方法）相比如何？

   • Q2：结合了 DIFFPOOL 的 GNN 对比图分类任务中的 SOTA 方法（包括 GNN 方法和 kernel-based 方法）相比如何？

   • Q3：DIFFPOOL 是否在输入的图上计算得到有意义且可解释的聚类？

2. 数据集：蛋白质数据集，包括ENZYMES, PROTEINS, D&D；社交网络数据集 REDDIT-MULTI-12K ；科学协作数据集COLLAB 。

   对这些数据集，我们执行 10-fold 交叉验证来评估模型性能，并报告 10 个 fold 的平均分类准确率。

3. 模型配置：在我们的实验中，用于 DIFFPOOL 的 GNN 模型是建立在 GraphSAGE 架构之上的，因为我们发现GraphSAGE 比标准的 GCN 效果更好。

   • 我们使用 GraphSAGE 的 mean 变体，并在我们的体系架构中每隔两个 GraphSAGE layer 之后应用一个 DIFFPOOL layer 。在每个 DIFFPOOL 层之后、下一个DIFFPOOL 层（或者 readout 层）之前，我们添加3 层图卷积层。

     这里感觉前后矛盾，就是是 3 层图卷积层还是 2 层图卷积层？要看代码。

   • 数据集一共使用 2 个 DIFFPOOL 层。对于小型数据集（如 ENZYMES, COLLAB），1 个 DIFFPOOL 层就可以实现相似的性能。

   • embedding 矩阵和 assignment 矩阵分别由两个单独的 GraphSAGE 模型计算。

   • 在 2 个 DIFFPOOL 层的体系架构中，cluster 数量设置为 DIFFPOOL 之前节点数量的 25% ；在 1 个 DIFFPOOL 层的体系架构中，cluster 数量设置为 DIFFPOOL 之前节点数量的 10% 。

   • 在GraphSAGE 的每一层之后都应用了 batch normalization 。

   • 我们还发现，在每一层的节点 embedding 中添加 $l_2$$l_2$ 正则化可以使得训练更加稳定。

   • 所有模型都训练最多 3000 个 epoch，并基于验证损失来执行早停策略。

   • 我们还评估了 DIFFPOOL 的两个简化版本：

     • DIFFPOOL-DET：是一个DIFFPOOL 的变体，其中使用确定性的图聚类算法来生成 assignment 矩阵。

     • DIFFPOOL-NOLP：是一个 DIFFPOOL 的变体，其中移除链接预测的辅助目标。

   另外，我们还将在 Structure2Vec 架构上测试了 DIFFPOOL 的类似变体，从而演示如何将 DIFFPOOL 应用于其它 GNN 模型。

4. baseline 方法：这里我们考虑使用不同了池化的 GNN方法，以及 SOTA 的 kernel-based 方法。

   • GNN-based 方法：

     • 带全局均值池化的 GraphSAGE。其它GNN 变体被忽略，因为根据经验，GraphSAGE 在任务中获得更高性能。

     • Structure2Vec:S2V 是一种SOTA 的graph representation learning方法，它将一个潜在变量模型（latent variable model）和 GNN 相结合，并使用全局均值池化。

     • ECC 将边信息融合到 GCN 模型中，并使用一个图粗化算法来执行池化。

     • PATCHYSAN 对每个节点定义一个感受野，并使用规范化的节点顺序，从而对节点embedding 的序列应用卷积。

     • SET2SET 使用 Set2Set 方法来代替传统 GNN 架构中的全局均值池化。这里我们使用 GraphSAGE 作为 base GNN model 。

     • SORTPOOL 应用GNN 架构，然后执行单层 soft pooling 层，然后对排序的节点 embedding 执行一维卷积。

     对于所有 GNN baseline，我们尽可能使用原始作者报告的 10-fold 交叉验证的结果。如果作者没有公开结果，则我们从原始作者获取代码运行模型，并根据原始作者的准则执行超参数搜索。

     对于 GraphSAGE 和 SET2SET，我们像 DIFFPOOL 方法一样使用基本的实现和超参数择优。

   • kernel-based 算法：我们使用 GRAPHLET、SHORTEST-PATH 、WEISFEILERLEHMAN kernel:WL、 WEISFEILER-LEHMAN OPTIMAL ASSIGNMENT KERNEL:WLOA 等方法。

     对于每个kernel ，我们计算归一化的 gram 矩阵。我们使用 10-fold 交叉验证，并使用 LISVM 计算分类准确率。超参数 C 的搜索范围 $\{{10}^{-3},{10}^{-2},\cdots ,{10}^2,{10}^3\}$$\{10^{-3},10^{-2},\cdots,10^2,10^3\}$ 。WL 和 WL-OA 的迭代范围从 0 到 5。

5. 下表给出了实验结果，这为 Q1 和 Q2 给出了正面的回答。最右侧的 Gain 列给出了相对于GraphSAGE 方法在所有数据集上的平均性能提升。

   可以看到：

   • DIFFPOOL 方法在 GNN 的所有池化方法中获得了最好的性能，在 GraphSAGE 体系结构上平均提升 6.27% ，并且在 5 个 benchmark 上的 4 个达到了 SOTA 。

   • 有趣的是，我们的简化模型变体 DIFFPOOLDET 在 COLLAB 数据集上达到了 SOTA 性能。这是因为 COLLAB 的很多协作图仅显示了单层社区结构，这些结构可以通过预先计算的图聚类算法很好地捕获。

   

6. 有一个现象是：尽管性能有了显著提升，但是 DIFFPOOL 可能无法稳定训练。并且即使采用相同的超参数设置，不同运行之间的准确率也存在着差异。可以看到添加链接预测目标可以使得训练更加稳定，并减少不同运行之间准确率的标准差。

7. 除了 GraphSAGE 之外，DIFFPOOL 也可以应用于其它GNN 架构，从而捕获图数据中的层次结构。为此我们在 Structure2Vec:S2V 上应用了 DIFFPOOL。

   我们使用三层的 S2V 架构：

   • 在第一个变体中，在S2V 的第一层之后应用一个 DIFFPOOL 层，并在 DIFFPOOL 的输出的顶部堆叠另外两个S2V 层。

   • 在第二个变体中，在S2V 的第一层、第二层之后分别应用一个 DIFFPOOL 层。

   在这两个变体中，S2V 模型用于计算 embedding 矩阵，而 GraphSAGE 模型用于计算assignment 矩阵。

   实验结果如下所示。可以看到： DIFFPOOL 显著改善了 ENZYMES 和 D&D 数据集上 S2V 的性能。

   在其它数据集上也观察到类似的趋势。结果表明：DIFFPOOL 是一个可以提升不同 GNN 架构的通用池化策略。

   

8. 尽管DIFFPOOL 需要对 asignment 矩阵进行额外的计算，但我们观察到 DIFFPOOL 实际上并不会带来大量的额外运行时间。这是因为每个 DIFFPOOL 层都通过粗化来减小了图的大小，从而加快了下一层中图的卷积操作。

   具体而言，我们发现带有 DIFFPOOL 的 GraphSage 模型要比带有 SET2SET 池化的 GraphSage 模型快 12 倍，并且仍能实现明显更高的准确率。

9. 为回答问题Q3， 我们通过可视化不同层中的 cluster assignment 来调研 DIFFPOOL 是否学习有意义的节点聚类。下图给出 COLLAB 数据集中，第一层和第二层的节点分配的可视化，其中：

   • 节点颜色表示cluster 成员关系。节点的 cluster 成员关系是通过对cluster assignment 的概率取argmax 来确定的。

   • 虚线表示簇关系。

   • 下图是三个样本的聚类（每个样本代表一个 graph），图 (a) 给出两层的层次聚类，图 (b),(c) 给出一层的层次聚类。

   • 注意，尽管我们将簇的数量设置为前一层节点的 25% ，但是 assignment GNN 可以自动学习适当数量的、且有意义的簇，从而分配给这些不同的图。（即大量的簇没有分配到任何节点）。

   可以看到：

   • 即使仅基于图分类目标，DIFFPOOL 仍可以捕获层次的社区结构。我们还通过链接预测辅助目标观察到cluster assignment 质量的显著提升。

   • 稠密的子图结构 vs 稀疏的子图结构：我们观察到 DIFFPOOL 学会了以非均匀方式将所有节点折叠（collapse）为 soft cluster，并且倾向于将稠密的子图折叠为簇。

     • 由于 GNN 可以有效地对稠密的、clique-like 的子图执行消息传递（由于较小的直径），因此在这种稠密的子图中将节点池化在一起不太可能导致结构信息的丢失。这直观地解释了为什么折叠稠密子图是 DIFFPOOL 的有效池化策略。

     • 相反，稀疏子图可能包含许多有趣的结构，包括路径、循环、树状结构，并且由于稀疏性导致的大直径，GNN 消息传递可能无法捕获这些结构。因此，通过分别池化稀疏子图的不同部分，DIFFPOOL 可以学习捕获稀疏子图中存在的有意义的结构。

   • 相似representation 节点的分配：由于assignment network 基于输入节点及其邻域特征来计算 soft cluster assignment，因此具有相似的输入特征和邻域结构的节点将具有相似的cluster assignment。

     实际上，可以构造一个人工case：其中两个节点尽管相距很远，但是它们具有相同的节点特征和邻域特征。这种情况下，pooling GNN 迫使它们分配到同一个cluster 中。这和其它体系结构中的池化概念完全不同。在某些情况下，我们确实观察到不相连的节点被池化到一起。

     另外，我们观察到辅助链接预测目标有助于阻止很远的节点池化到一起。并且，可以使用更复杂的 GNN 聚合函数（诸如高阶矩）来区分结构相似和特征相似的节点，总体的框架保持不变。

   • 预定义聚类数的敏感性：我们发现assignment 根据网络深度和 $C$$C$ （最大的聚类簇数量）而变化。使用较大的 $C$$C$ ，则 pooling GNN 可以对更复杂的层次结构进行建模，但是会导致更大的噪声和更低的训练效率。

     尽管 $C$$C$ 是一个预定义的参数，但是pooling GNN 通过端到端训练来学习使用适当数量的 cluster。具体而言，assignment 矩阵可能不会用到某些簇。对于未被使用的 cluster 对应的矩阵列，它在所有节点上都具有较低的值。例如图2(c) 中，节点主要分配到 3 个簇上。